package string;

import java.util.LinkedList;

/**
 * @author Liaorun
 */
public class ExpressionCompute {

    public static void main(String[] args) {
        System.out.println(getValue("1*(2+3)+1"));
    }

    public static int getValue(String str) {
        return value(str.toCharArray(), 0)[0];
    }

    /**
     * 请从str[i...]往下算，遇到字符串终止位置或者右边括号，就停止
     *
     * @param str
     * @param i
     * @return 0）负责的这一段的结果是多少 1）负责的这一段计算到了那个位置
     */
    private static int[] value(char[] str, int i) {
        LinkedList<String> que = new LinkedList<>();
        int num = 0;
        int[] bra;

        while (i < str.length && str[i] != ')') {
            if (str[i] >= '0' && str[i] <= '9') {
                num = num * 10 + str[i++] - '0';
            } else if (str[i] != '(') {
                // 遇到的时运算符号
                addNum(que, num);
                que.addLast(String.valueOf(str[i++]));
                num = 0;
            } else {
                // 遇到左括号，交给递归的子过程处理
                bra = value(str, i + 1);
                num = bra[0];
                // 从子过程处理的结束位置 + 1开始计算，
                // + 1是跳过末尾的 ) 右括号
                i = bra[1] + 1;
            }
        }

        addNum(que, num);

        return new int[]{getNum(que), i};
    }

    /**
     * 队列中只有数字和 + -号这种情况，时计算最终的结果
     * exampes: 1+1—1
     *
     * @return 算数运算结果
     */
    private static int getNum(LinkedList<String> que) {
        int res = 0;
        boolean add = true;
        String cur = null;
        int num = 0;
        while (!que.isEmpty()) {
            cur = que.pollFirst();
            if ("+".equals(cur)) {
                add = true;
            } else if ("-".equals(cur)) {
                add = false;
            } else {
                num = Integer.parseInt(cur);
                res += add ? num : (-num);
            }
        }

        return res;
    }

    private static void addNum(LinkedList<String> que, int num) {
        if (!que.isEmpty()) {
            int cur;
            // 弹出栈顶的字符
            String top = que.pollLast();

            if ("+".equals(top) || "-".equals(top)) {
                // 如果是 + or - 将符号在放回去
                que.addLast(top);
            } else {
                // 如果是 * or /
                // 在弹出一个数字
                cur = Integer.parseInt(que.pollLast());
                // 按照运算规则计算，覆盖传入进来的值
                num = "*".equals(top) ? (cur * num) : (cur / num);
            }
        }

        // 把传进来的数字加到队列
        que.addLast(String.valueOf(num));
    }
}
